package LeetCode._02_数组;

public class _304_二维区域和检索_矩阵不可变 {
    class NumMatrix {

        //定义preSum[i][j]preSum[i][j] 表示 从 [0,0][0,0] 位置到 [i,j][i,j] 位置的子矩形所有元素之和。
        private int[][] preSum;
        public NumMatrix(int[][] matrix) {
            int row = matrix.length;
            int col = matrix[0].length;
            if(row == 0 || col == 0) return;
            preSum = new int[row+1][col+1];
            for(int i=1;i<=row;i++){
                for(int j=1;j<=col;j++){
                    //使用图表示
                    preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1];
        }
    }


}
